#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include "../include/linkedlist.h"
  
    /* Add Elements to the Binary Search Tree */
    void insertBst(struct fileDescriptor *data ) {
       
        struct node1* newNode = (struct node1*) malloc(sizeof (struct node1));
        struct node1* temp;
        struct node1* tempParent;

	if(bstrootcreated=0)
	{
	root1=NULL;
        bstrootcreated=1;
	}


        char full_path[100];
        /*concatenate file name with 
the file path*/
        if(strcmp(data->locationPath,"/")!=0)
        {
            strcpy(full_path,data->locationPath);
            //strcat(full_path,"/");
            //strcat(full_path,data->fileName);
        }
        else
        {
            //strcpy(full_path,"/");
            //strcat(full_path,data->fileName);
        }
       
        /*adding data to newNode*/
        strcpy(newNode->locationPath,full_path);
        newNode->filefd  = data;
        newNode->left = NULL;
        newNode->right = NULL;
        newNode->parent = NULL;
        //printf("newnode data %s\n",newNode->full_path);
        if(root1 == NULL){
           root1 = newNode;
        }
        else{
            temp = root1;
            tempParent = NULL;
            while(temp){
                 if( strcmp( newNode->locationPath ,temp->locationPath) ==0 ){
                    //printf("duplicate--\n");
                    temp = NULL;
                }
                else{
                    if( strcmp( newNode->locationPath ,temp->locationPath) <0 ){
                        tempParent = temp;
                        temp = temp->left;
                    }
                    else{
                        tempParent = temp;
                        temp = temp->right;
                    }
                }
            }
            newNode->parent = tempParent;

            if( strcmp( newNode->locationPath,tempParent->locationPath) <0 ){
                tempParent->left =newNode;
            }
            else
            {
                tempParent->right = newNode;
                //printf (" right %s \n", newNode->full_path);
            }
        }
    }
   /*Inorder traversal of BST*/
    void inorder(struct node1 *t){
        struct node1 *temp;
        temp = t;
        if(temp){
            inorder(temp->left);
            //printf("\n %s \n",temp->locationPath);
            inorder(temp->right);
        }
    }
  
   /*Display elements in the BST*/
    void displayList(){
	//printf("\n In BST-------\n");
        struct node1 *temp = root1;
        if(root1 == NULL)
	{;
            //printf("empty tree\n");
	}
        else
            inorder(temp);
    }
     //-----------------------------------------------------------------------------------------------------------------
/*Inorder traversal of BST*/
    void inorder_deletion(struct node1 *t){
        struct node1 *temp;
        temp = t;
        if(temp==NULL)
	return 0;

            inorder_deletion(temp->left);
     
            inorder_deletion(temp->right);
		free(temp);
        
    }
  
   /*Display elements in the BST*/
    void flushBst(){
	
        struct node1 *temp = root1;
        if(root1 == NULL)
           {
;
//printf("empty tree\n");
}
        else
            inorder_deletion(temp);
    }
//-----------------------------------------------------------------------------------------------------------------
    struct node1* searchBstRec(struct node1 *t,char *data){
       
        if(t == NULL || (strcmp(data,t->locationPath) ==0)){
            return t;
        }
        else
        {
           
            if( strcmp( data,t->locationPath) <0 ){
                return searchBstRec(t->left,data);
            }
            else
            {
                return searchBstRec(t->right,data);
            }
         }
    }
    /* Search  Element in the List */
    int searchBst(char *data){
        struct node1 *t = root1;
        struct node1 *temp = searchBstRec(t,data);
        if(temp == NULL) {
            //printf("element is not present");
            return Failure;
        }
        else
        {
            //printf("element is present");
            return Success;
        }
    }

	struct fileDescriptor * searchBstfd(char *data){
        struct node1 *t = root1;
        struct node1 *temp = searchBstRec(t,data);
        if(temp == NULL) {
            //printf("element is not present");
            return NULL;
        }
        else
        {
            //printf("element is present");
            return temp->filefd;
        }
    }
   
   
    /*transplant function for delete function. It transplants node11 with node12*/
    void transplantTree(struct node1 *node11,struct node1 *node12){
       
        if(node11->parent == NULL){
            root1 = node12;
        }
        else{
            
            if(node11 == node11->parent->left){
                node11->parent->left = node12;
            }
            else
            {
                
                node11->parent->right = node12;
            }
        }
        if(node12 != NULL)
        {
               
                node12->parent = node11->parent;
        }
    }
   
   
    /* searches the minimum value node and returns the same.*/
    struct node1* treeMin(struct node1 *m){
        while(m->left != NULL){
            m = m->left;
        }
        //printf("%s",m->locationPath);
        return m;
    }
  
  
    /* Delete  Element  from the Binary Search Tree */
    void deleteBstElm(char *data){

	
        struct node1* location;
        struct node1* successor=NULL;
       
        location = searchBstRec(root1,data);

	//printf("In the deleteBST\n");

        if(location != NULL){
            //printf("element is present\n");
           
            if(location->left == NULL){
                transplantTree(location,location->right);
            }
            else{
                  
                    if(location->right==NULL){
                        transplantTree(location,location->left);
                    }
                    else{
                       
                         successor = treeMin(location->right);
                      
                        if(successor->parent != location){
                           
                            transplantTree( successor, successor->right);
                          
                            successor->right = location->right;
                            successor->right->parent =  successor;
                        }
                       
                        transplantTree(location, successor);
                       
                        successor->left = location->left;
                        successor->left->parent = successor;
                        successor->parent = location->parent;
                      
                    }
            }
          
            free(location);
        }
        else
        {
           
            //printf("element is not present\n");
        }
    }
  /*
    int main(){
       int location;
        char text[] = "text";
        char fileName[] = "abc.txt";
        char locationPath[] = "/";
        struct fileDescriptor* data = (struct fileDescriptor*)malloc(sizeof(struct fileDescriptor));
        if(data!=NULL){
		data->fileSize = 10;
		data ->blockNumber = 1;
		strcpy(data->fileType,text);
		strcpy(data -> fileName, fileName);
		strcpy(data -> locationPath,locationPath);
		insertBst(data);
		}
      
       
      
        printf ("List Contents: \n");
        displayList();
        printf("element search \n");
        char data8[]= "/abc.txt";  
        location = searchBst(data8);
        if(location == Success){
            printf("element is present\n");
        }
        else
        {
            printf("element is not present\n");
        }
        printf("element delete:\n");
        char data9[]= "/abc.txt";  
       deleteBstElm(data9);
        displayList();
      
        return 0;
    } 

*/
